#include <stdlib.h>
#include <stdio.h>
#include <string.h> // C string, not C++ string
#include "graph.h"
#include "auxiliares-grasp.h"

/**
 * calcula el costo de un path respecto a una matriz de costos
 * @param path
 * @param costo
 * @return 
 */
float calcularCosto(std::list<int> path, int** costos) {
    float costo = 0;
    bool hayAnterior=false;
    int anterior;

    for (list<int>::iterator itList = path.begin(); itList != path.end(); itList++) {
        if (hayAnterior) {
            costo += costos[*itList][anterior];
        } else {
        	hayAnterior=true;
            anterior = *itList;
        }
    }
    return costo;
};

//int largoPath(int*);

Graph * ConstructionPhase(Graph * G, int** C, int k) {
    //grafo solucion con nodos terminales
    Graph* Gsol = new Graph(G);
    //
    //    //armo una lista con todas las parejas de nodos terminales -- no esta en el pseudo codigo
    //    std::list<par> * m;
    //    int cantTerminalesSinAnalizar = largoPath(G->_T);
    //    for (int i = 0; i < cantTerminalesSinAnalizar; i++) {
    //        for (int j = i + 1; j < cantTerminalesSinAnalizar; j++) {
    //            par p;
    //            p.x = i;
    //            p.y = j;
    //            m->push_front(p);
    //        }
    //    }
    //
    //    bool ExistMijSinAnalizar = true;
    //    //loop principal del pseudo codigo
    //    while (ExistMijSinAnalizar) {
    //        //elejir ij random
    //        int random = rand() % cantTerminalesSinAnalizar + 0; // random entre 0 y cantTerminales
    //
    //        //creamos la matriz de costos C techo.		
    //        int** Ct = new int*[G->tamanioG];
    //        for (int u = 0; u < G->tamanioG; u++) {
    //            Ct[u] = new int[G->tamanioG];
    //            for (int v = 0; v < G->tamanioG; v++) {
    //                if (Gsol->existeArista(u, v)) {
    //                    Ct[u][v] = 0;
    //                } else {
    //                    Ct[u][v] = C[u][v];
    //                }
    //            }
    //        }
    //        //obtenemos los k caminos mas cortos entre i y j con menos de d hops (yen tuneado)
    //       // std::list<Path> * L1 = Yen(G, Ct, m[random]);
    //        int**  L1 = Yen(G, Ct, m[random]);
    //        //si existe un p con costo 0 usamos ese, sino elegimos uno al azar	
    //        existe = false;
    //        Path p1;
    //        for (list<int>::iterator it = L1; it != L1->end() || existe; ++it) {
    //            float costo = calcularCosto(it, Ct);
    //            if (costo == 0) {
    //                p1 = it;
    //                existe = true;
    //            }
    //        }
    //        if (!existe) {
    //            int random1 = rand() % L1->size - 1 + 0; // random entre 0 y largo L1 -1
    //            p1 = L1[random1];
    //        }
    //
    //        // Aca tenemos p1 y lo agregamos a Gsol
    //        //Gsol->agregarPath(list<int> p1); // esto puede cambiar 
    //
    //        Graph Gt = Graph(G);
    //        Gt.quitarPath(p1); //salvo extremos
    //        //creamos la matriz de costos C techo2.		
    //        int** Ct2 = new int*[G->tamanioG];
    //        for (int u = 0; u < G->tamanioG; u++) {
    //            Ct2[u] = new int[G->tamanioG];
    //            for (int v = 0; v < G->tamanioG; v++) {
    //                if (Gsol->existeArista(u, v))
    //                    Ct2[u][v] = 0;
    //                else
    //                    Ct2[u][v] = C[u][v];
    //            }
    //        }
    //        //obtenemos los k caminos mas cortos entre i y j con menos de d hops (yen tuneado)
    //        std::list<Path> * L2 = Yen(Gt, Ct2, m[random]);
    //        //si existe un p con costo 0 usamos ese, sino elegimos uno al azar	
    //        bool existe = false;
    //        Path p2;
    //        for (list<int>::iterator it = L2; it != L2->end() || existe; ++it) {
    //            int costo = calcularCosto(it, Ct);
    //            if (costo == 0) {
    //                p2 = it;
    //                existe = true;
    //            }
    //        }
    //        if (!existe) {
    //            int random1 = rand() % L2->size - 1 + 0; // random entre 0 y largo L1 -1
    //            p2 = L2[random1];
    //        }
    //
    //        m->remove(m[random]);

    //update matrxi
    //remove internal keypath
    //    }
    //return 0;// new graph;
    return Gsol;
};
